﻿public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public TreeNode ConstructMaximumBinaryTree(int[] nums)
    {
        return CreateTree(nums, 0, nums.Length - 1);
    }

    private TreeNode CreateTree(int[] nums, int left, int right)
    {
        if (left > right) return null;

        int maxIndex = left;
        for (int i = left+1; i <= right; i++)
        {
            if (nums[i] > nums[maxIndex]) maxIndex = i;
        }

        TreeNode node = new TreeNode(nums[maxIndex]);

        int left_left = left;
        int left_right = maxIndex - 1;
        node.left = CreateTree(nums, left_left, left_right);

        int right_left = maxIndex + 1;
        int right_right = right;
        node.right = CreateTree(nums, right_left, right_right);
        return node;
    }

    public static void Main(string[] args)
    {
        int[] nums = [3, 2, 1, 6, 0, 5];
        
        Solution solution = new Solution();
        TreeNode rootNode = solution.ConstructMaximumBinaryTree(nums);
        
        // 前序遍历
        PreOrderPrint(rootNode);
    }

    private static void PreOrderPrint(TreeNode rootNode)
    {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        if (rootNode is not null) stack.Push(rootNode);
        TreeNode node;
        while (stack.Count > 0)
        {
            node = stack.Pop();
            Console.Write($"{node.val} ");
            if (node.right is not null) stack.Push(node.right);
            if (node.left is not null) stack.Push(node.left);
        }
    }
}